<?php
/**
 * Created by PhpStorm.
 * User: Administrator
 * Date: 2017/6/15
 * Time: 16:38
 */
class Sort extends Base{

    /**
     * 冒泡排序  (n-1)+(n-2)+...+2+1 = n(n-1)/2 次比较 最多 (n-1)+(n-2)+...+2+1 = n(n-1)/2 次交换
     * @return array
     */
    protected function maopaoSort()
    {
        $this->name = '冒泡排序';
        $arr = $this->arr;
        $count = count($arr);
        for($i=0;$i<$count;$i++){
            for ($j=$count-1;$j>$i;$j--){
                if($arr[$j]>$arr[$j-1]){
                    $tmp = $arr[$j];
                    $arr[$j] = $arr[$j-1];
                    $arr[$j-1] = $tmp;
                }
            }
        }
        return $arr;
    }

    /**
     * 选择排序 需要进行 (n-1)+(n-1)+(n-2)+...+1 = n(n-1)/2次比较和最多 n-1次交换 复杂度O(n^2)
     * @return array
     */
    protected function selectSort(){
        $this->name = '选择排序';
        $arr = $this->arr;
        $count = count($arr);
        for ($i=0;$i<$count;$i++){
            $max = $i;
            for($j=$i+1;$j<$count;$j++){
                if($arr[$j]>$arr[$max]){
                    $max = $j;
                }
            }

            $tmp = $arr[$i];
            $arr[$i] = $arr[$max];
            $arr[$max] = $tmp;

        }
        return $arr;
    }


    /**
     * 插入排序 需进行1+2+...+(n-1) = n(n-1)/2 次比较 和 最多 n(n-1)/2 次交换 复杂度O(n^2)
     */
    protected function insertSort()
    {
        $this->name = '插入排序';
        $arr = $this->arr;
        $count = count($arr);
        for($i = 1;$i<$count;$i++){
            $tmp = $arr[$i];
            for($j = $i-1;$j>=0;$j--){
                if($tmp>$arr[$j]){
                    $arr[$j+1] = $arr[$j];
                    $arr[$j] = $tmp;
                }else{
                    break;
                }
            }
        }
        return $arr;
    }

    




}





















